Network devices, such as switches and/or routers, are designed to forward network traffic, in the form of packets, at high line rates. One of the most important considerations for handling network traffic is packet throughput. To accomplish this, special-purpose processors known as network processors have been developed to efficiently process very large number of packets per second. In order to process a packet, the network processor (and/or network equipment employing the network processor) needs to extract data from a packet header indicating destination of the packet, class of service, etc., store the payload data in memory, perform packet classification and/or queuing operations, determine a next hop for the packet, select an appropriate network port to forward the packet, etc. These operations are generally referred to as “packet processing” operations.
In addition to the foregoing packet forwarding operations, there may be a need to search packet payloads for a given string or a set of strings. For example, security applications may need to search for certain strings indicative of a virus or Internet worm that is present in the packet payload, such as for load balancing and/or billing purposes.
Searching packet payloads presents a problem with respect to line-rate packet forwarding. The reason for this is that string searches may be very time consuming, especially, if the strings are relatively long. With the network line rates significantly increasing every year, it is becoming increasingly difficult for software and/or hardware based solutions to operate at these increasing line rates.
One of the current techniques monitors signatures in a network packet payload by storing a predefined signature of a predetermined length in one of a plurality of traditional Bloom filters. Further, a data stream on the network is monitored for a signature which corresponds to the predefined signature. Furthermore, using an analyzer, whether the network signature corresponds to the predefined signature and is a false positive, is determined. These techniques, using the Bloom filters, are used for pattern matching applications, such as network security, application specific service differentiation, QoS enhancement and/or network engineering and so on.
Current techniques also use counting Bloom filters that substitute bit-array with a counter-array to maintain per-flow statistics, such as packet/byte count and the like. Each entry in a bit-array is replaced with an n-bit wide counter in the counting Bloom filters. Also, each time a packet arrives, the Bloom filters apply Bloom hash function, generate an index I and a counter that is indexed by I in the Bloom array is incremented.
However, this process imposes the need for an n-bit wide data bus to transfer the counter content back and forth from the Bloom hash function unit. Further, such implementations can be hardware intensive as they may require a large number of Bloom filter hash units, increase in the width of the data-bus to support counter-fields that can result in noticeable speed reduction for a wide-bit vector. In addition, these techniques can require complicated Application Specific Integrated Circuit (ASIC) layout. Furthermore, Bloom filters can require a wide bit array for long string bit searches that can result in significant hardware complexity.
Other features of the present embodiments will be apparent from the accompanying drawings and from the detailed description that follows.